public class Solution236 {
    TreeNode res;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        contains(root, p, q);
        return res;
    }

    int contains(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return 0;
        }
        int left = contains(root.left, p, q);
        int right = contains(root.right, p, q);
        if (left == 3 || right == 3) {
            return 3;
        }
        if (root == p) {
            if (left == 2 || right == 2) {
                res = root;
                return 3;
            } else {
                return 1;
            }
        }
        if (root == q) {
            if (left == 1 || right == 1) {
                res = root;
                return 3;
            } else {
                return 2;
            }
        }
        int ans = left | right;
        if (ans == 3) {
            res = root;
        }
        return ans;
    }
}
